#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int backpack01(vector<int>& nums, int target, int dp[]);
int findTargetSumWays(vector<int>& nums, int S);
int findTargetSumWays(vector<int>& nums, int S) {
    int sum = 0;
    for (unsigned int i = 0; i < nums.size(); i++) {
        sum += nums[i];
    }
    if (S > sum || (S + sum) % 2 != 0){
        return 0;
    }
    int x = (S + sum) / 2;
    if (x < 0) return 0;
    int dp[x + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;

    return backpack01(nums, x, dp); 
}
int backpack01(vector<int>& nums, int target, int dp[]) {
    for (unsigned int i = 0; i < nums.size(); i++) {
        for (int j = target; j > nums[i] - 1; j--) {
            dp[j] = dp[j] + dp[j - nums[i]];
        }
    }
    return dp[target];
}

int main(){
    vector<int> nums = {1, 1, 1, 1, 1};
    int S = 3;
    cout << findTargetSumWays(nums, S) << endl;
    return 0;
}